package lesson9;

import java.util.Arrays;

public class mergeSort {

		public static void main(String[] args) {

			int[] array = {9,5,4,80,6,7,0,10};
			System.out.println(Arrays.toString(array));
			array = doMergeSort(array);
			System.out.println(Arrays.toString(array));
		}

		private static int[] doMergeSort(int[] array) 
		{
			//if elements in array > 1 (element 1 is already sorted)
			if(array.length == 1)
				//else return array
				return array;
			else
			{
				//1: devide array into 2 arrays
				int[] array1 = new int[array.length/2];
				int[] array2 = new int[array.length-array1.length];
				//2: populate the new arrays with the values from the array
				for(int i = 0; i < array.length; i++)
				{
					if(i < array.length/2)
					{
						array1[i] = array[i];
					}
					else
					{
						array2[i-array2.length] = array[i];
					}
				}
				//3: sort the arrays using doMergeSort
				array1 = doMergeSort(array1);
				array2 = doMergeSort(array2);
				
				//4: check each value from the 2 arrays and combine them into a new one
				int i = 0;//index of first subarray
				int j = 0;//index of second subarray
				int k = 0;//index of main array
				
				while(i < array1.length && j < array2.length)
				{
					if(array1[i] < array2[j])
					{
						array[k] = array1[i];
						k++;
						i++;
					}
					else
					{
						array[k] = array2[j];
						k++;
						j++;
					}
				}
				//one of the subarrays may be still containing solitary values. Insert them into the main array
				if(i < array1.length)//the non empty subarray is array1
				{
					for(int p = i; p < array1.length; p++)
					{
						array[k] = array1[p];
						k++;
					}
				}
				
				if(j < array2.length)//the non empty subarray is array2
				{
					for(int p = j; p < array2.length; p++)
					{
						array[k] = array2[p];
						k++;
					}
				}
				
				
			}
			return array;
		}
}
